package com.huangyi;

public class Main {
    public static void main(String[] args) {
        // 测试用例
    }

    // 删除并获得点数
    static class Solution {
        public int deleteAndEarn(int[] nums) {
            // 1) 找到数组最大值，确定统计数组范围
            int max = 0;
            for (int num : nums) {
                max = Math.max(max, num);
            }

            // 2) 统计每个数字出现的次数
            int[] count = new int[max + 1];
            for (int num : nums) {
                count[num]++;
            }

            // 3) 动态规划：f[i] 选择数字 i 的最大分数，g[i] 不选数字 i 的最大分数
            int[] f = new int[max + 1];
            int[] g = new int[max + 1];

            // 4) 状态转移
            for (int i = 1; i <= max; i++) {
                f[i] = g[i - 1] + count[i] * i; // 选 i 则不能选 i-1
                g[i] = Math.max(f[i - 1], g[i - 1]); // 不选 i 则取前一个的最大值
            }

            // 5) 返回最终结果
            return Math.max(f[max], g[max]);
        }
    }
}